package cn.com.mdx.collection.queue;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * <p> 双端队列 - 链表实现
 *
 * @author ：huangy
 * @date ：Created in 2020/8/14 5:48 下午
 */
public class LinkedDeque<Item> implements Iterable<Item> {

    /**
     * 容量
     */
    private int size;

    /**
     * 队列头指针
     */
    private Node<Item> first;

    /**
     * 队列尾指针
     */
    private Node<Item> last;

    /**
     * 节点类
     */
    private static class Node<Item> {
        private final Item item;
        private Node<Item> pre;
        private Node<Item> next;

        public Node(Item item, Node<Item> pre, Node<Item> next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    /**
     * @param item 入队列数据
     * @return void
     * @Author huangy
     * @description //TODO 从队列头加入数据
     * @date 5:16 下午 2020/8/12
     **/
    public void addFirst(Item item) {
        Node<Item> oldFirst = first;
        first = new Node<>(item, null, oldFirst);
        if (isEmpty()) last = first;
        else oldFirst.pre = first;
        size++;
    }

    /**
     * @param item 入队列数据
     * @return void
     * @Author huangy
     * @description //TODO 从队列尾加入数据
     * @date 5:16 下午 2020/8/12
     **/
    public void addLast(Item item) {
        Node<Item> oldLast = last;
        last = new Node<>(item, oldLast, null);
        if (isEmpty()) first = last;
        else oldLast.next = last;
        size++;
    }

    /**
     * @return Item 返回的数据
     * @Author huangy
     * @description //TODO 从队列头移除数据
     * @date 5:17 下午 2020/8/12
     **/
    public Item removeFirst() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        Item item = first.item;
        first = first.next;
        if (first != null) first.pre = null;
        size--;
        return item;
    }

    /**
     * @return Item 返回的数据
     * @Author huangy
     * @description //TODO 从队列为移除数据
     * @date 5:17 下午 2020/8/12
     **/
    public Item removeLast() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        Item item = last.item;
        last = last.pre;
        if (last != null) last.next = null;
        size--;
        return item;
    }

    /**
     * @return int 队列容量
     * @Author huangy
     * @description //TODO 队列容量
     * @date 5:18 下午 2020/8/12
     **/
    public int size() {
        return size;
    }

    /**
     * @return boolean true 表示空 false 表示不为空
     * @Author huangy
     * @description //TODO 查看队列是否为空
     * @date 5:18 下午 2020/8/12
     **/
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return java.util.Iterator
     * @Author huangy
     * @description //TODO 获取队列迭代器
     * @date 5:20 下午 2020/8/12
     **/
    @Override
    public Iterator<Item> iterator() {
        return new LinkedDequeIterator();
    }

    /**
     * 迭代器
     */
    private class LinkedDequeIterator implements Iterator<Item> {
        Node<Item> tail = first;

        @Override
        public boolean hasNext() {
            return tail != null;
        }

        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException("元素不存在无法遍历");
            Item item = tail.item;
            tail = tail.next;
            return item;
        }
    }

    public static void main(String[] args) {
        LinkedDeque<Integer> linkedDeque = new LinkedDeque<>();
        linkedDeque.addFirst(2);
        linkedDeque.addFirst(1);
        linkedDeque.addLast(3);
        linkedDeque.addLast(4);
        for (Integer i : linkedDeque) {
            System.out.println(i);
        }
        System.out.println("-----------------");
        System.out.println(linkedDeque.removeFirst());
        System.out.println(linkedDeque.removeFirst());
        System.out.println(linkedDeque.removeLast());
        System.out.println("-----------------");
        linkedDeque.addLast(100);
        linkedDeque.addFirst(101);
        for (Integer i : linkedDeque) {
            System.out.println(i);
        }
    }

}
